package com.lw.leetcode.other.c;

/**
 * Created with IntelliJ IDEA.
 * 906. 超级回文数
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/12 16:59
 */
public class SuperpalindromesInRange {

    public static void main(String[] args) {
        SuperpalindromesInRange test = new SuperpalindromesInRange();

        // 4
        String left = "4";
        String right = "100000000000000000";

        int i = test.superpalindromesInRange(left, right);
        System.out.println(i);
    }

    public int superpalindromesInRange(String left, String right) {
        long a = Long.parseLong(left);
        long b = Long.parseLong(right);
        long st = (long) Math.pow(a, 0.5);
        long end = (long) Math.pow(b, 0.5);
        if (st * st < a) {
            st++;
        }
        long first = getFirst(st);
        if (first < st) {
            first = getNext(first);
        }
        int count = 0;
        for (long i = first; i <= end; i = getNext(i)) {
            if (check(i * i)) {
                count++;
            }
        }
        return count;
    }

    private int[] items = new int[18];

    private boolean check(long value) {
        int index = 0;
        while (value != 0) {
            items[index++] = (int) (value % 10);
            value /= 10;
        }
        int a = 0;
        int b = index - 1;
        while (a < b) {
            if (items[a] != items[b]) {
                return false;
            }
            a++;
            b--;
        }
        return true;
    }

    private long getFirst(long value) {
        if (value < 10) {
            return value;
        }
        if (value < 100) {
            long t = value / 10;
            return t * 10 + t;
        }

        if (value < 1000) {
            long t = value / 10;
            return t * 10 + getRe(value / 100);
        }
        if (value < 10000) {
            long t = value / 100;
            return t * 100 + getRe(value / 100);
        }
        if (value < 100000) {
            long t = value / 100;
            return t * 100 + getRe(value / 1000);
        }
        if (value < 1000000) {
            long t = value / 1000;
            return t * 1000 + getRe(value / 1000);
        }
        if (value < 10000000) {
            long t = value / 1000;
            return t * 1000 + getRe(value / 10000);
        }
        if (value < 100000000) {
            long t = value / 10000;
            return t * 10000 + getRe(value / 10000);
        }
        if (value < 1000000000) {
            long t = value / 10000;
            return t * 10000 + getRe(value / 100000);
        }
        return 999999999;
    }

    private long getNext(long value) {
        if (value < 10) {
            if (value == 9) {
                return value + 2;
            }
            return value + 1;
        }
        if (value < 100) {
            if (value == 99) {
                return value + 2;
            }
            long t = value / 10 + 1;
            return t * 10 + t;
        }
        if (value < 1000) {
            if (value == 999) {
                return value + 2;
            }
            long t = value / 10 + 1;
            return t * 10 + t / 10;
        }
        if (value < 10000) {
            if (value == 9999) {
                return value + 2;
            }
            long t = value / 100 + 1;
            return t * 100 + getRe(t );
        }
        if (value < 100000) {
            if (value == 99999) {
                return value + 2;
            }
            long t = value / 100 + 1;
            return t * 100 + getRe(t / 10);
        }
        if (value < 1000000) {
            if (value == 999999) {
                return value + 2;
            }
            long t = value / 1000 + 1;
            return t * 1000 + getRe(t);
        }
        if (value < 10000000) {
            if (value == 9999999) {
                return value + 2;
            }
            long t = value / 1000 + 1;
            return t * 1000 + getRe(t / 10);
        }
        if (value < 100000000) {
            if (value == 99999999) {
                return value + 2;
            }
            long t = value / 10000 + 1;
            return t * 10000 + getRe(t );
        }
        if (value < 1000000000) {
            if (value == 999999999) {
                return value + 2;
            }
            long t = value / 10000 + 1;
            return t * 10000 + getRe(t / 10);
        }
        return 1000000001;
    }

    private long getRe(long value) {
        long item = 0;
        while (value != 0) {
            item = item * 10 + value % 10;
            value /= 10;
        }
        return item;
    }

}
